/*
题目描述
Given a positive integer n (3 ≤ n ≤ 90), count all possible distinct binary strings of length n such that there are no consecutive 1’s.

输入格式
A single integer n.

输出格式
A single integer representing the number of distinct binary strings of length n without consecutive 1’s.

输入样例
2
输出样例
3

*/

#include <iostream>
#include <vector>
using namespace std;

long long countBinaryStrings(int n) {
    vector<long long> dp0(n + 1, 0);
    vector<long long> dp1(n + 1, 0);

    dp0[1] = 1;
    dp1[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp0[i] = dp0[i - 1] + dp1[i - 1];
        dp1[i] = dp0[i - 1];
    }

    return dp0[n] + dp1[n];
}